#include <vector>
#include <iostream>

using namespace std;

vector<string> res; //记录返回数组

void recursion(int n, string str, int left, int right)
{
    //终止条件  n对括号，递归 2*n 次。 -->判断左右括号数量是否都为n
    if (right == n && left == n)
    {
        res.push_back(str);
        return;
    }

    //处理过程
    if (left < n) //左括号的数量 不超过n 对数
    {
        // left += 1;
        // str += "(";
        //向下一层
        recursion( n, str + "(", left + 1, right);
    }

    if (right < left /*&& right < n*/)
    {
        // right += 1;
        // str += ")";
        //向下一层
        recursion( n, str + ")", left, right + 1);
    }
}

vector<string> generateParenthesis(int n)
{

    //recursion
    int left = 0;
    int right = 0;
    string str = "";

    recursion( n, str, left, right);

    return res;
}

int main ()
{
    vector<string> vs = generateParenthesis(3);

    for(auto v:vs)
        cout<<v<<"      ";
    
    return 0;
}